package xyf.p11.other.slidewindow;

import java.util.HashMap;
import java.util.Map;

/**
 * ClassName: P0076_MinWindow
 * Description:
 * Author: xyf
 * Date: 9/9/22 10:19 AM
 * Version: 1.0
 **/
public class P0076_MinWindow
{
    public String minWindow(String s, String t)
    {
        HashMap<Character, Integer> sMap = new HashMap<>();

        HashMap<Character, Integer> tMap = new HashMap<>();

        for (int i = 0; i < t.length(); i++)
        {
            Integer value = tMap.getOrDefault(t.charAt(i), 0);
            tMap.put(t.charAt(i), value + 1);
        }

        int slow = 0;
        int fast = 0;
        String res = "";
        int min = Integer.MAX_VALUE;
        while (fast < s.length())
        {
            if (fast - slow >= t.length())
            {
                if (contain(sMap, tMap))
                {
                    if (fast - slow < min)
                    {
                        min = fast - slow;
                        res = s.substring(slow, fast);
                    }
                    Integer value = sMap.getOrDefault(s.charAt(slow), 0);
                    sMap.put(s.charAt(slow), value - 1);
                    slow++;
                    continue;
                }
            }

            Integer value = sMap.getOrDefault(s.charAt(fast), 0);
            sMap.put(s.charAt(fast), value + 1);
            fast++;

        }

        while (true)
        {
            if (fast - slow >= t.length())
            {
                if (contain(sMap, tMap))
                {
                    if (fast - slow < min)
                    {
                        min = fast - slow;
                        res = s.substring(slow, fast);
                    }
                    Integer value = sMap.getOrDefault(s.charAt(slow), 0);
                    sMap.put(s.charAt(slow), value - 1);
                    slow++;
                    continue;
                }
                break;
            }
            break;
        }

        return res;
    }

    private boolean contain(HashMap<Character, Integer> sMap, HashMap<Character, Integer> tMap)
    {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet())
        {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            Integer cur = sMap.get(key);
            if (cur == null || cur < value)
            {
                return false;
            }
        }
        return true;
    }
}